package Test_1125;

import Test_1120.BinaryTree;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Test {

    //寻找是否有该元素
    public boolean isfindVal(BinaryTree.TreeNode root,int val){
        //是否有节点
        if(root==null){
            return false;
        }
        //在左子树查找
        if(isfindVal(root.left,val)){
            return true;
        }
        //在右子树查找
        if(isfindVal(root.right,val)){
            return true;
        }
        return false;
    }
    public boolean isSameTree(BinaryTree.TreeNode p, BinaryTree.TreeNode q) {
        //判断结构是否相同
        if(p!=null && q==null|| p==null &&q!=null){
            return false;
        }
        //如果相同，想判断是否为空
        //判断是否为空，如果都为空，直接返回
        if(p==null && q==null){
            return true;
        }
        //判断值是否相同
        if(q.val!=p.val){
            return false;
        }
        //都不为空且值相同
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //另一棵树的子树
    public boolean isSubtree(BinaryTree.TreeNode root, BinaryTree.TreeNode subRoot) {
        if(root==null){
            return false;
        }
        //判断节点是否相同
        if(isSameTree(root,subRoot))
            return true;
        //如果不相同，判断该节点左子树是否相同
        if(isSubtree(root.left,subRoot))
            return true;

        //如果不相同判断该节点右子树是否相同
        if(isSubtree(root.right,subRoot))
            return true;
        return false;
    }


    //翻转二叉树
    //不用考虑左右子树为不为空，直接翻转即可
    public BinaryTree.TreeNode invertTree(BinaryTree.TreeNode root) {
        if(root==null){
            return null;
        }
        //将左右子树进行翻转
        BinaryTree.TreeNode tmp=null;
        tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public int getHeight(BinaryTree.TreeNode root){
        if(root==null){
            return 0;
        }
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);
        return Math.max(leftheight,rightheight)+1;
    }
    //平衡二叉树：左右子树相差<=1
    //求左右子树的高度
    public boolean isBalanced(BinaryTree.TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        //左子树和右子树是否也是平衡二叉树
        //Math.abs绝对值
        return Math.abs(leftHeight-rightHeight)<2
                &&isBalanced(root.left)&&isBalanced(root.right);
    }

}
